freenode_mathfandomcom-20200215-history
Introduction to Category Theory
Topic The aim was a gentle introduction to Category theory, although in the end only the definition of "Category" and a few examples were presented. Seminar 21:00:10 ChanServ changed the topic of #mathematics to: SEMINAR IN PROGRESS: Introduction to Category Theory by _llll_ | If you want to ask a question, type "!" and wait till be asked 21:00:37 _llll_: so, um, yeah, everyone shuts up now and i begin 21:01:02 _llll_: right 21:01:19 _llll_: welcome everyone to the first, of potentially a few seminars on various topics 21:01:31 _llll_: this is kind of a learning process for everyone so it may go horribly wrong 21:01:54 _llll_: so im going to give a very basic introduction to category theory, not assuming any prior knowledge 21:02:09 _llll_: so this means that there wont be anything particularly advanced in it 21:02:28 _llll_: in particular im not really going to answer quetions such as "why should i study catgeory theory?" 21:02:55 _llll_: because category theory is just like any other part of mathematics -- if you dont know why you are studying it, you probably dont need to be 21:03:01 _llll_: so, onwards 21:03:14 _llll_: So the first section is a definition of "a category 21:03:36 _llll_: often people call categories by single script letters, so \mathcal{C} in latex 21:03:55 _llll_: so im going to call my category "CC" which stands for "C in script" 21:04:17 _llll_: so a category CC consists of a few different things 21:04:25 _llll_: the first are called "objects" 21:04:38 _llll_: im going to use A,B,C,... to refer to the objects 21:05:06 _llll_: these things are just some sort of mathamtical ojects, so sets or whatever -- it's not so important, you just need to know that a category Cc has a collection of objects 21:05:45 _llll_: people write things like Ob(CC) for the collection of all objects in CC, and say things like "A is in CC" to mean "A is one of the objects in CC" 21:06:23 _llll_: As well as objects, CC also has "morphism" (also called "maps", or "arrows") 21:06:39 _llll_: im going to use lower case letters like a,b,c,f,g,h to refer to maps 21:06:56 _llll_: and we can write Arrows(CC) to mean "the collection of all maps in CC" 21:07:19 _llll_: every map has to have a "start" (or "domain") and an "end" (or "codomain") object 21:07:44 _llll_: so if f is a map, the domain of f is an object and the codomain is another object (or maybe even the same object) 21:08:03 _llll_: we write f:A-->B to mean "f is a map that starts at A and ends at B" 21:08:13 _llll_: there are likely many maps that start at A and end at B 21:08:32 _llll_: we write Hom_CC(A,B) to be "the set of all maps going from A to B" 21:08:41 _llll_: you also see notation like CC(A,B) 21:09:25 _llll_: it's best if we assume that these sets CC(A,B) are all disjoint -- so if f is an arrow then f is in CC(A,B) for precisely one pair A,B of objects 21:09:41 kommodore: ! 21:09:44 _llll_: so Arrows(CC) is the union of all the different CC(A,B) 21:09:49 _llll_: kommodore: go ahead 21:10:09 kommodore: Is it necessary that CC(A,B) is a set? 21:10:35 _llll_: it's not strictly necessary, but it is usually the case that it is 21:10:44 kommodore: thanks 21:10:51 _llll_: generally CC(A,B) is a set but Ob(CC) is not a set 21:10:58 invariable: _llll_, when you use the term "map" here do you mean a function ? 21:11:05 _llll_: the categories where all the CC(A,B) are sets are called "locally small" 21:11:06 invariable: or some more specific meaning 21:11:19 _llll_: no, "map" is something that is being defined along with CC 21:11:40 invariable: thanks 21:11:48 _llll_: so CC has a bunch of things called "map"s, but these things are not necessarily functions 21:12:05 _llll_: just like the "objects" are not necessarily sets 21:12:18 Lapper: Oh, thanks. I thought I was missing something when I had no idea what a map was. :P 21:12:45 Manyfold: ! 21:12:51 _llll_: go ahead Manyfold 21:13:25 Manyfold: you wrote there are many maps between A and B but aren't these maps identical? 21:13:35 _llll_: no, definitely not 21:13:51 _llll_: ill come to some examples in a bit, it may make things clearer 21:14:07 _llll_: ok, so so far ive said that CC has a load of "objects" and "maps", and that every map has a starting object and an ending object 21:14:50 _llll_: suppose that f:A-->B and g:B-->C are two maps in CC. then to continue the definition, we have to have a "composite" 21:15:17 _llll_: this means that whenever f:A-->B and g:B-->C there is a new map which i'll write (f#g) which goes from A to C 21:15:32 _llll_: think of this as "f followed by g" 21:15:57 _llll_: if you like sets and functions, then # is a function from CC(A,B)xCC(B,C) --> CC(A,C) 21:16:34 _llll_: we can only compose two maps if one ends where the second starts 21:16:51 _llll_: so if y:D-->E then we cant form f#y unless D=B 21:16:55 ~zachk: ! 21:17:00 _llll_: go ahead zachk 21:17:07 ~lxuser: ! 21:17:18 ~zachk: in the sets and function example is x cartesianProduct? 21:17:27 _llll_: yes, (sorry) 21:17:42 _llll_: lxuser: what was your question? 21:17:49 ~lxuser: is the (f#g) notation standard? 21:18:14 _llll_: no, not really. actually there are a million different notations in category theory 21:18:30 ~lxuser: iirc, one usually sees (g . f) for function composition 21:18:36 _llll_: somtimes people call it "g o f" (which is what you use in set theory for "composition of functions") 21:18:49 ~dtog: or just gf 21:18:53 _llll_: i prefer f#g because f happens first 21:19:04 _llll_: and it emphasises that these things arent necessarily functions 21:19:48 ~lxuser: _llll_, yes, following paths is a better intuition perhaps. thanks 21:20:35 _llll_: ok, so quick recap: to specify a category CC we have to give: a collection of objects (A,B,C,...), a collection of maps (f,g,h,....), such that every map has a start and end object, and whenever 2 maps are composable (A--f-->B---g-->C), we can compose these into a (f#g):A-->C 21:20:41 _llll_: we're still not finished 21:20:49 _llll_: this composition has to be "associative" 21:21:10 _llll_: this means that if we have three maps A--f-->B--g-->C--h-->D 21:21:25 _llll_: then the maps (f#g)#h and f#(g#h) have to be equal 21:21:39 _llll_: ie it doesnt matter what order we join the three maps f,g,h 21:21:54 _llll_: there's one last part of the definition then we can look at some examples 21:22:11 vixey: ! 21:22:16 _llll_: go ahead vixey 21:22:34 vixey: Do you define equality of maps per category or how? 21:22:49 _llll_: well, we assume that we can tell when things are equal or not 21:23:01 vixey: (what does it mean for one map to be equal to another?) 21:23:10 _llll_: basically, jsut assume that you can always tell 21:23:23 _llll_: im trying not to go too far into overly-technical foundational issues 21:24:05 _llll_: the last part of the definition is that for all objects A in CC, there has to be a designated map A-->A called "the identity on A", which we write as id_A 21:24:17 _llll_: and this has to satisfy the following conditions 21:24:37 _llll_: if a:A-->B is any map, then id_A # a has to be equal to a 21:24:54 _llll_: and if c:C-->A is any map, then c#id_A =c 21:25:16 ~zachk: ! 21:25:20 _llll_: go ahead zachk 21:25:34 ~zachk: is id_A the "identity map"? 21:25:43 _llll_: yeah, it's "the identity on A" 21:26:04 _llll_: so if b is another object we'll have "the identity on B", which is written id_B and it goes id_B:B-->B 21:26:11 _llll_: so id_A=id_B iff A=B 21:27:08 ~DWarrior-: ! 21:27:16 _llll_: go ahead DWarrior- 21:27:25 ~DWarrior-: is id_A unique? 21:27:39 _llll_: yes, i was just coming to that :) 21:27:51 ~DWarrior-: ok 21:28:03 _llll_: so i should probably say at this point, that there is a uniqueness property here: if x:A-->A is any map which has the proeprties that x#a=a and b#x=b for all a and b as above, then necessarily x=id_A 21:28:37 _llll_: the proof is exactly the same way that you prove that the identity is unique in a group or ring or any other algebriac sturcture you've studied before 21:28:51 _llll_: so i'll leave that as an exercise 21:29:13 _llll_: let's look at some examples, as it may make things clearer 21:29:51 _llll_: The first example is the category called "Set". objects of Set are sets, maps in Set are functions, so f:A-->B means f is a function A to B 21:30:31 _llll_: composition is what you expect -- just composition of functions, and the identity on A sends a to a 21:31:11 _llll_: so obviosuly we'd need to show that composition is associative and identities have the required properties, but that's not hard to do, so i wont go through that here 21:32:10 _llll_: i'll just say that this is why we dont demand that Ob(CC) is a set, since Ob(Set) is not a set 21:32:36 _llll_: there are a bunch of simialr examples, eg the category of groups (it's often written as "Grp" for some reason). here the objects are groups, and the maps are group homomorphisms 21:32:52 Manyfold: does Ob(set) include itself? 21:32:55 bwr: ! 21:33:04 _llll_: go ahead bwr 21:33:20 bwr: is Ob(Set) not a set because it is not well defined or for some other reason? 21:33:46 _llll_: basically the definition of "set" means that you have to construct sets out of other, previously constructed sets 21:34:02 bwr: ah ok, thanks 21:34:05 _llll_: this is what i referred to as a "technical foundational issue" before 21:34:19 Manyfold: ! 21:34:26 _llll_: we'll just assume that Ob(Set) is a "collection" (or "proper class") 21:34:29 _llll_: go ahead Manyfold 21:34:34 Manyfold: does Ob(set) include itself? 21:34:54 _llll_: no, becayse Ob(Set) is the collection of all sets, and Ob(Set) is not a set 21:35:04 Manyfold: k 21:35:26 _llll_: these are good questions to ask, but i kind of want to ignore them -- for a proper answer you can look up "Grothendieck universe" on wikipedia 21:36:18 _llll_: so anyway, as i was saying, we can get a category Grp where the objects are groups and the maps are group homomorphisms 21:37:09 _llll_: or more generally, if you have some algebriac structure (like a ring/monoid/semigroup/magma/module) there is likely a category where those structures are the objectsm and the structure preserving homomorphisms are the maps 21:37:19 _llll_: but i wont say too much about that 21:37:26 _llll_: for a "smaller" example 21:37:42 _llll_: suppose G is any single, fixed group. 21:38:08 _llll_: so that means G is a set with a mutliplication and the multiplication is associative and admits a unit 21:38:42 _llll_: we can build a category GG where we take one single object (say {*} ) 21:39:07 _llll_: and for every element g of the group GG, we will take one map g :{*}-->{*} 21:40:01 _llll_: we need to say how to compose these things, and since there is only one object, every pair of maps are composable, as we have {*} -- g --> {*} -- h --> {*} where g and h are elements of G 21:40:14 _llll_: the composition is defied as g#h=gh 21:40:29 _llll_: where gh is "g multiplied by h" using the multiplication in G 21:40:45 _llll_: this is associative because multiplication in G is associative 21:41:25 _llll_: there is only one object, so we only need to define one identity, namely id_{*}. and we define id_{*} to be 1 the map corresponding to the unit in the group G 21:41:57 _llll_: you can check that "1 is a unit in the group G" means exactly that 1 is the identity on {*} in GG 21:42:34 _llll_: so what im saying here, is that a group can be regarded as a category with one object 21:43:27 _llll_: actually, in a group, every element must be invertible but we never used that -- a "monoid" is defined the same way as "group", but without the requirement that everything be invertible 21:43:37 _llll_: so the natural numbers under addition are a monoid but not a group 21:44:00 _llll_: and given a monoid M, we can defome a category MM with one object. 21:44:16 _llll_: and it is not hard to see that *every* category with one object gives us a monoid 21:44:38 _llll_: (the elements are the maps from the category.. i'll leave the rest as an exercise) 21:45:03 _llll_: so "monoids" are exactly the same as "categories with one object" 21:45:24 ~zachk: ! 21:45:29 _llll_: go ahead zachk 21:45:54 ~zachk: did monoids get 'discovered' in category theory, or are they from some other branch of mathematics? 21:46:07 _llll_: monoids were known well before categories 21:47:21 _llll_: (oh, and you can turn this on its head, and say that a category is a "monoid with many objects") 21:47:32 _llll_: so a different kind of "small" example comes from partially ordered sets 21:47:55 _llll_: a partially ordered set is a set P and a relation "<=" on P 21:48:42 _llll_: this has to be reflexive, meaning that x<=x for all x in P 21:48:58 _llll_: and transitive meaning that if x,y,z are in P with x<=y<=z then x<=z 21:49:15 _llll_: we can build a category corresponding to P as follows 21:49:25 _llll_: for objects take the elements of P 21:49:41 _llll_: (so if we call the partially ordered set P, and the category PP, then Ob(PP)=P) 21:49:51 ~lxuser: ! 21:49:58 _llll_: go ahead lxuser 21:50:54 ~lxuser: by a "monoid with many objects" do you mean a monoid action on the set of objects? 21:51:21 _llll_: no, i just mean that you can think of a category as a generalisation of the notion of monoid 21:52:00 _llll_: so if you understand something about monoids, you can likely apply that understanding to categories. it's an analagy basically 21:52:47 _llll_: ok, so to continue with PP, we had Ob(PP)=P, so we are going to have lots of objects, one for each element of P 21:53:07 _llll_: and for maps, if x<=y in P, we will add exactly one map x-->y to PP 21:53:40 _llll_: so we can only have a pair of compsoable maps x-->y-->z if x<=y<=z 21:54:04 _llll_: but then x<=z by transitivity, so we define the composite of the maps to be the unique map x-->z in PP 21:54:46 _llll_: (since there's at most one map between every pair of objects in PP, im not giving these things names. we culd call the map x-->y "(x,y)" if we liked) 21:55:28 _llll_: associativity is easy, and the identity map on the object x is the map correspondng to the statement that x<=x 21:56:13 _llll_: so this shows that partially ordered sets give another example of categories. so category theory is a generalisation of the notion of "one partially ordered set" *and* of "a group" 21:57:21 _llll_: ok, so it's now about an hour in. i was going to talk about products, but probably it's best to leave that for another time, since 60mins of mathematics is enough for anyone. instead do people have any questions? 21:57:36 ~zachk: ! 21:57:45 _llll_: go ahead 21:57:58 ~zachk: if i kind of get monoids, how far am I from monads? 21:58:06 _llll_: not very actually 21:58:25 ~steven__: ! 21:58:28 _llll_: to define monad you need to define "functor" and "natural transformation" which take a while 21:58:40 _llll_: there is a sense in which a monad is a special kind of monoid 21:58:57 ~lxuser: zachk, monoids are easy in that elements of a monoid can be represented by "strings" in the formal language sense. 21:59:08 _llll_: steven__: go ahead 21:59:12 ~steven__: can you give another example, where objects aren't sets like in the last example 22:00:04 _llll_: ok, for objects take points on a plane (ie elements of R^2) 22:00:17 _llll_: and a map from one point to another is a path on the plane 22:00:29 _llll_: composition means "join paths together" 22:00:47 _llll_: and the identity is the "path of length zero", ie the "do nothing" path 22:01:42 _llll_: if you know what topological spaces are, then you can replace "the plane" with any topological space, X, and "paths on the plane" with continuous maps from the inverval 0,1 to X 22:01:57 _llll_: this is called the "fundamental infinity groupoid on X" 22:02:45 kommodore: I suppose the category Top of topological spaces and continuous maps is another example 22:03:18 _llll_: usually people have preferred to identify homotopyic paths, and then you get "the fundamental groupoid on X", and even more usually you pick a point x in X and require the paths to start and end at x, so there's just one object -- so we have a monoid (and in fact a group, since you can reverse paths -- it's the "fundamental group" at x) 22:04:34 _llll_: i guess people who like programming in ML or haskell like the example of the "category of types", where the objects are types and maps A to B are functions that take one variable of type A and give an output of type B 22:05:52 ~DWarrior-: ! 22:05:56 _llll_: go ahead 22:05:59 vixey: is there any analogue of a category for dependent types? 22:06:07 ~DWarrior-: I must have missed it, because I still don't know if id_A is unique 22:06:32 ~DWarrior-: if I think of it as path from point A to point A, it doesn't have to be unique 22:07:15 kommodore: id_A=id_A#id'_A=id'_A 22:07:20 _llll_: if x:A-->A has the properties (1) and (2) where 1) is that whenever a:B-->A then a#x=a and 2) is that whenever y:A-->C then x#y=y, then x=id_A 22:07:38 _llll_: with the path example, the identity is the path that has length zero, ie "do nothing" 22:08:10 _llll_: other paths are just maps A-->A only the identity has the properties (1) and (2) 22:08:33 ~DWarrior-: ah, ok 22:09:18 _llll_: maybe next week i will talk about how to do "cartesian products" in a general category, and talk about "universal properties" 22:10:48 Manyfold: so next week your seminar will continue? 22:11:06 ~DWarrior-: is the seminar over officially? 22:11:06 _llll_: yeah, unless anyone else has a burning desire to talk about something else 22:11:53 ~lxuser: wouldn't it be better to define functors and natural transformations first? 22:12:00 bwr: _llll_: thanks, i enjoyed the seminar 22:12:03 _llll_: hmm, possibly 22:12:36 _llll_: i guess there's two options, one is to talk about universal proeprties, one is to tlak about natural transformations and the yoneda lemma 22:41:43 ChanServ changed the topic of #mathematics to: NEXT SEMINAR: Sunday 13 July at 20:00 UTC Functors and Natural Transformations by _llll_ 22:43:27 * ~zachk thanks _llll_ for the seminar 22:43:47 _llll_: then the week agfter i will try and get something different 22:46:25 ~DWarrior-: thanks for the seminar 22:46:26 _llll_: thanks for everyone for coming, especially people who asked questions 22:47:26 _llll_: if anyone has any suggestions on how to improve things, im listening 22:47:32 shminux: when is the transcript going to be posted? 22:47:40 shminux: if at all 22:47:43 _llll_: oh, good point Category:Seminar Category:Category Theory